// https://leetcode.cn/problems/replace-all-s-to-avoid-consecutive-repeating-characters/description/

// 算法思路总结：
// 1. 遍历字符串检测问号位置
// 2. 尝试用小写字母替换问号
// 3. 确保替换字母与相邻字符不同
// 4. 时间复杂度：O(26n)，空间复杂度：O(1)

#include <iostream>
using namespace std;

#include <string>

class Solution 
{
public:
    string modifyString(string s) 
    {
        int n = s.size();
        for (int i = 0 ; i < n ; i++)
        {
            // 1.先判断是否是问号
            if (s[i] == '?')
            {
                // 2.再判断位置
                for (char ch = 'a' ; ch <= 'z' ; ch++)
                {
                    if ((i == 0 || s[i - 1] != ch) && (i == n - 1 || s[i + 1] != ch))
                        s[i] = ch;
                }
            }
        }
        return s;
    }
};

int main()
{
    string s1 = "?zs", s2 = "ubv?w";
    Solution sol;

    cout << sol.modifyString(s1) << endl;
    cout << sol.modifyString(s2) << endl;

    return 0;
}